<?php
/**
 * @title 981. 基于时间的键值存储 - 二分查找
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class TimeMap {
    /**
     * Initialize your data structure here.
     */
    function __construct() {
        $this->List = [];
    }

    /**
     * @param String $key
     * @param String $value
     * @param Integer $timestamp
     * @return NULL
     */
    function set($key, $value, $timestamp) {
        /**
         * @since 2021-07-10 入队
         */
        $this->List[$key][] = [$value, $timestamp];

        /**
         * @return
         */
        return null;
    }

    /**
     * @param String $key
     * @param Integer $timestamp
     * @return String
     */
    function get($key, $timestamp) {
        /**
         * @since 2021-07-10 是否存在
         */
        if(!isset($this->List[$key])){
            return "";
        } else {
            /**
             * @since 2021-07-10 二分查找
             */
            $s = 0;
            $e = count($this->List[$key])-1;

            /**
             * @since 2021-07-10 先处理 t>=e, t<s
             */
            if($timestamp >= $this->List[$key][$e][1]){
                return $this->List[$key][$e][0];
            } elseif($timestamp < $this->List[$key][$s][1]) {
                return "";
            } else {
                /**
                 * @since 2021-07-10 范围 s <= t < e
                 */
                while($e-$s > 1){
                    $mid = ($s+$e)>>1;
                    $val = $this->List[$key][$mid][1];

                    if($timestamp >= $val){
                        $s = $mid;
                    } else {
                        $e = $mid;
                    }
                }

                /**
                 * @return
                 */
                return $this->List[$key][$s][0];
            }
        }
    }
}

/**
 * @url http://127.0.0.1/leetcode/202107/2021.07.10.php
 */
$datas = [
    [
        ["TimeMap","set","get","get","set","get","get"],
        [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]],
    ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
// foreach ($datas as $data){
//     var_dump($data);
//
//     $obj = new Solution();
//     $result = $obj->(...$data);
//     // $result = $obj->($xhprof->tree($data));
//     // $result = $obj->($xhprof->listNode($data));
//     // $result = $obj->find(...$data);
//     var_dump($result);
//     // if(count($result)<=20){
//     //     var_dump($result);
//     // } else {
//     //     var_dump(count($result));
//     // }
//     echo str_repeat(PHP_EOL, 3);
//     echo str_repeat("<br>", 3);
// }

foreach ($datas as $data){
    $obj = new $data[0][0](...$data[1][0]);

    for ($i=1; $i<count($data[0]); $i++){
        $func = $data[0][$i];
        $param = $data[1][$i];
        $result = $obj->$func(...$param);

        echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
            if($result === true){
                echo "True";
            } elseif($result === false) {
                echo "False";
            } elseif($result === null) {
                echo "Null";
            } elseif(is_array($result)) {
                var_dump($result);
            } else {
                echo $result;
            }
        echo PHP_EOL;
    }

    echo str_repeat(PHP_EOL, 3);
}
$xhprof->end();
